import java.util.Queue;

public class Solution {

    public static void exchange(int left, int right, int[] array){
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
    public static int partition(int start, int end, int[] array){
        int base = start;
        //选择第o个作为基准
        start = start+1;
        int left=start;
        int right = end;
        while(left<=right){
            while(left<=right && array[left]<=array[base])left++;
            while(left<=right && array[right]>array[base])right--;
            if(left<right){
                exchange(left,right,array);
                left++;
                right--;
            }
        }
        exchange(base,left-1,array);
        return base;
    }
    public static void QuickSort(int start, int end, int[] array){
        if(start>=end)return;
        int base = partition(start, end, array);
        QuickSort(0,base-1,array);
        QuickSort(base+1,end,array);
    }
    public static void main(String args[]){
        int[] array={7,4,8,5,3,4,5,2,6};
        QuickSort(0, array.length-1, array);
        System.out.println();
    }

}

